#include "..\CookHeader.h"

int maxWeight = 7;      // 賶 ִ 
int rowCount = 4;       //  
Array <int> weight = { 0, 5, 3, 4, 6 };     //  (0, , , , ݱ)
Array <int> money = { 0, 12, 6, 8, 13 };    //  (0, , , , ݱ)

int knapsack() {
    println("## ޸̼ 迭 ##");

    Array <Array <int>> memoAry;
    memoAry = emptyArray2(rowCount + 1, maxWeight + 1); //  迭 غ

    for (int row = 1; row < rowCount + 1; row++) {
        print(to_string(row) + " -->");               // 1~4(4ȸ)
        for (int col = 1; col < maxWeight + 1; col++) { // 1col KG ~ 7col KG
            if (weight[row] > col) {  //  ԰  ũ ==  濡  
                memoAry[row][col] = memoAry[row - 1][col];
            }
            else { //  濡 
                int value1 = money[row] + memoAry[row - 1][col - weight[row]];
                int value2 = memoAry[row - 1][col];
                memoAry[row][col] = max(value1, value2);
            }
            printf("%3d", memoAry[row][col]);
        }
        println("");
    }
    return memoAry[rowCount][maxWeight];
}

int main() {
    int maxValue = knapsack();
    println("\n賶   ִ  ִ  -->" + to_string(maxValue) + " ");
}